package problem207_Course_Schedule;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

public class Solution {
	private Map<Integer, List<Integer>> graph;
	int[] visitStatus;

	public boolean canFinish(int numCourses, int[][] prerequisites) {
		this.graph = new HashMap<>();
		this.visitStatus = new int[numCourses];
		for (int[] s : prerequisites) {
			if (graph.containsKey(s[1])) {
				graph.get(s[1]).add(s[0]);
			} else {
				graph.put(s[1], new LinkedList<>());
				graph.get(s[1]).add(s[0]);
			}
		}
		for (int i = 0; i < numCourses; i++) {
			if (visitStatus[i] == 0) {
				if (!dfs(i))
					return false;
			}
		}
		return true;
	}

	private boolean dfs(int i) {
		// 0:unVisited,1:visiting,2:visited
		visitStatus[i] = 1;
		List<Integer> adj = graph.get(i);
		if (adj != null) {
			for (int j : adj) {
				if (visitStatus[j] == 1)
					return false;
				else if (visitStatus[j] == 0 && !dfs(j))
					return false;
			}
		}
		visitStatus[i] = 2;
		return true;
	}
}
